The present invention relates to the field of data processing and more particularly to method and apparatus for caching data in a data processing system.
Cache memories are relatively small, high-speed memories used to reduce memory access time in modern computer systems. The idea is to store data from frequently accessed regions of system memory in cache memory so that subsequent accesses to the cached regions will not incur the full system memory access time, but the shorter cache access time instead. A memory transaction that accesses cache memory instead of system memory is called a cache hit, and the cache xe2x80x9chit ratexe2x80x9d is a fundamental metric of cache design.
FIG. 1 illustrates a prior art cache memory 12 that includes a data store 14 and a tag store 16. In effect, the cache memory 12 is a data buffer in which each entry in the data store 14 is mapped to a region of system memory by a corresponding entry in the tag store 16. When an address is asserted to system memory, set and tag fields within the address are used to determine whether an entry in the cache memory 12 is mapped to the region of system memory sought to be accessed. The set field (sometimes called an index) is decoded to select an entry in the data store 14 and a corresponding entry in the tag store 16. An address value, called a xe2x80x9ctag,xe2x80x9d is output from the selected tag store entry and compared with the tag field of the asserted address. If the tag field of the asserted address matches the tag output from the selected tag store entry, a cache hit is signaled to indicate that the selected entry in the data store is mapped to the region of system memory sought to be accessed. In the case of a memory read operation, a cache line (i.e., the unit of information in a cache) is output from the selected entry in the data store and returned to the requestor. Low order bits of the input address may be used to select a sub-portion of the cache line according to the width of the transfer path to the requestor and the width of data that can be handled by the requester. Write requests are handled similarly, except that data is written to the selected entry in the data store 14.
The cache memory 12 is referred to as a direct mapped cache because only one cache line is stored in the cache for each possible value of the set field. That is, system memory is directly mapped to the cache based on the set field so that there is only one tag field in the tag store 16 per value of the set field. One undesirable consequence of direct mapping is that a cache miss will occur in response to each new memory address for which the set field, but not the tag field, matches a previously asserted address. Thus, if a sequence of memory accesses are directed to system memory addresses that have the same set fields but different tag fields, a significant number of cache misses will occur and data from the different system memory addresses will be frequently swapped into and out of the cache memory 12; a phenomenon called xe2x80x9cthrashing.xe2x80x9d An alternate mapping scheme, called multiple-way, set associative mapping, is used to avoid this sort of thrashing.
FIG. 2 illustrates a prior-art four-way, set associative cache memory 26 in which each set field is mapped to as many as four system memory addresses. Instead of a single data store, there are four data stores (28A-28D), called xe2x80x9cdata ways,xe2x80x9d and instead of a single tag store, there are four tag stores (30A-30D), called xe2x80x9ctag ways.xe2x80x9d In effect, the direct mapped operation described above occurs in parallel for each of the four data ways and four tag ways. When a memory address is received, the set field is used to select a respective cache line from each of the four data ways and also to select a respective tag from each of the four tag ways. Each of the selected tags is compared against the tag field of the input cache address to generate a corresponding tag way hit signal. The tag way hit signals are input to hit logic 31 which asserts or deasserts a cache hit signal based on whether any of the tag way hit signals indicates a match. Assuming a cache hit, the hit logic generates a data way select signal that indicates which of the tag ways contains the tag matching the tag field of the input address. The data way select signal is supplied to a multiplexer 32 to select the source of the cache line output to be the data way that corresponds to the tag way containing the tag matching the tag field.
Because the same set field is associated with multiple tag addresses in a multiple-way, set associative cache memory, the type of thrashing that can occur in direct mapped caches is usually avoided. Consequently, a multiple-way, set associative cache tends to achieve a higher hit rate than a direct mapped cache having the same sized data store. The higher hit rate is not without cost, however, because the increased logic required to generate the way select signal and to select one of the plurality of set-field-selected cache lines increases the overall time required to output a cache line. This is in contrast to a direct mapped cache which outputs a cache line as quickly as the set field can be decoded and the selected cache line can be driven onto the return data path.
An apparatus and method for accessing a cache memory are disclosed. A memory address is asserted that includes a set field and a tag field that together uniquely identify a region of system memory equal in size to a cache line in a cache memory. A partial tag field that includes less than all bits in the tag field is compared against a partial tag entry stored in the cache memory. A cache line is output from the cache memory if the partial tag field matches the partial tag entry.